package dynamicProgramming;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;





public class OptimalBST {
	public double [][] optimal;
	public String [][] roots;
	public List<String> keys;
	

	/**
	 * get the dynamic table
	 * @param file
	 * @return result
	 */
	public String probMatrix(List<Map.Entry <String,Double>> file){
		
		keys= new ArrayList<String>();
		
		for(int i=0; i < file.size();i++ ){
			keys.add(file.get(i).getKey());
		
		}
		
		
//		System.out.println(keys);
		
		
		optimal = new double [keys.size()+2][keys.size()+1];
		
		roots = new String[keys.size()+2][keys.size()+1];
		
	
		for(int i=1; i<= keys.size();i++){
			
			optimal[i][i-1] = 0d;
			
			
			optimal[i][i] = file.get(i-1).getValue();
			
			roots[i][i] = keys.get(i-1);
			
		}
		
		for(int d=1; d<keys.size();d++){
			
			for(int i=1; i<=keys.size()-d;i++){
				
				int j=i+d;
				
				double min = Double.POSITIVE_INFINITY;
				
				for(int k=i; k<=j;k++){
					
					double q = optimal[i][k-1]+ optimal[k+1][j];
					
					if( q < min){
						
						min = q;
						
						roots[i][j]=keys.get(k-1);
						
					}
					
				}
				
				//get sum
				double sum = file.get(i-1).getValue();
				
				for(int s =i+1; s<=j; s++){
					sum = sum + file.get(s-1).getValue();
					
					
				}
				
				optimal[i][j]=min+sum;
				
			}
			
			
			
			
		}
		
		
		
		
		String value = roots[1][keys.size()];
		
	
		
		
		return value ;
	}
	
	/**
	 * create BST
	 * @param 
	 */
	public Node OptimalBST(String value, List<Map.Entry <String,Double>> file){
		//get key in arraylist according to the value
		int key = keys.indexOf(value) +1;
		//get the probability according to the value from hashmap.
		
		
		
		double probability = file.get(keys.indexOf(value)).getValue();
		List<Integer> leftKeys = findLeft(key);
		List<Integer> rightKeys = findRight(key);
		Node root = new Node(value, key, probability,null,leftKeys, rightKeys);
		
		
		
		
		//left child
		
		if(root.leftNodes.size()!=0){
			int lstart = root.leftNodes.get(0);
			int lend = root.leftNodes.get(root.leftNodes.size()-1);
			String dataLeft = roots[lstart][lend];
			int keyLeft = keys.indexOf(dataLeft)+ 1;
			List<List<Integer>> split = splitKeys(keyLeft, root.leftNodes);
			
			double probabilityLeft = file.get(keys.indexOf(dataLeft)).getValue();
			root.left = new Node(dataLeft, keyLeft, probabilityLeft,root, split.get(0), split.get(1));
			OptimalBST(dataLeft, keyLeft, probabilityLeft, root, root.left, file);
		}
		
		
		//right child
		
		if(root.rightNodes.size()!=0){
			int rstart = root.rightNodes.get(0);
			int rend = root.rightNodes.get(root.rightNodes.size()-1);
			String dataRight = roots[rstart][rend];
			int keyRight = keys.indexOf(dataRight)+ 1;
			
			double probabilityRight = file.get(keys.indexOf(dataRight)).getValue();
			List<List<Integer>> split = splitKeys(keyRight, root.rightNodes);
			root.right = new Node(dataRight, keyRight, probabilityRight, root, split.get(0), split.get(1));
			OptimalBST(dataRight, keyRight, probabilityRight, root, root.right, file);
		}
		
		
		
		
	    
	    
		return root;
	}
	
	public void OptimalBST(String value, int key, double probability, Node parent, Node node, List<Map.Entry <String,Double>> file){
		
		if(node.leftNodes.size()!=0){
			int lstart = node.leftNodes.get(0);
			int lend = node.leftNodes.get(node.leftNodes.size()-1);
			String dataLeft = roots[lstart][lend];
			int keyLeft = keys.indexOf(dataLeft)+ 1;
			List<List<Integer>> split = splitKeys(keyLeft, node.leftNodes);
			double probabilityLeft = file.get(keys.indexOf(dataLeft)).getValue();
			node.left = new Node(dataLeft, keyLeft, probabilityLeft,node, split.get(0), split.get(1));
			OptimalBST(dataLeft, keyLeft, probabilityLeft, node, node.left, file);
		}
		
		if(node.rightNodes.size()!=0){
			int rstart = node.rightNodes.get(0);
			int rend = node.rightNodes.get(node.rightNodes.size()-1);
			String dataRight = roots[rstart][rend];
			int keyRight = keys.indexOf(dataRight)+ 1;
			double probabilityRight = file.get(keys.indexOf(dataRight)).getValue();
			List<List<Integer>> split = splitKeys(keyRight, node.rightNodes);
			node.right = new Node(dataRight, keyRight, probabilityRight, node, split.get(0), split.get(1));
			OptimalBST(dataRight, keyRight, probabilityRight, node, node.right, file);
		}
		
	
		
	}
	
	
	public List<List<Integer>> splitKeys(int key, List<Integer> list){
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> leftSide = new ArrayList<Integer>();
		List<Integer> rightSide = new ArrayList<Integer>();
		for(Integer element: list){
			if(key > element){
				leftSide.add(element);
			}else if(key < element){
				rightSide.add(element);
			}
		}
		
		result.add(leftSide);
		result.add(rightSide);
		return result;
	}
	//find the smallest and largest number
	public List<Integer> findLeft(int num){
		List<Integer> list = new ArrayList<Integer>();
		
		
		for(int i=1; i< num; i++){
				list.add(i);
		}
		Collections.sort(list);
		
		return list;
		
	}
	
	public List<Integer> findRight(int num){
		List<Integer> list = new ArrayList<Integer>();
		
		
		for(int i=num+1; i<=keys.size(); i++){
			
				list.add(i);
			
		}
		Collections.sort(list);
		
		return list;
		
	}
	
//	public List<Integer> findLeft(int key, int parentKey ){
//		List<Integer> list = new ArrayList<Integer>();
//		for(int i = parentKey+1; i < key ;i++){
//			list.add(i);
//		}
//		
//		Collections.sort(list);
//		
//		return list;
//	}
//	
//	
//	public List<Integer> findRight(int key, int parentKey ){
//		List<Integer> list = new ArrayList<Integer>();
//		for(int i = key+1; i < parentKey ;i++){
//			list.add(i);
//		}
//		
//		Collections.sort(list);
//		
//		return list;
//	}
	
	//build tree
//	public void buildTree(String value,Map<String,Double> file){
//		double prob = file.get(value);
//		String string = buildTree(value);
//		
//		
//	}
	
//	public String buildTree(Node node,String value, Map<String,Double> file ){
//		if(node == null){
//			node.value = value;
//			node.parent = null;
//			
//		}
//		
//		
//		
//		
//		return null;
//	}
	
//	//find left leave
//	public void leftLeaf(String value, Map<String,Double> file){
//		int k = keys.indexOf(value)+1;
//		roots[][k-1];
//		
//	}
	
	//find right leave
	
	    
	
	/**
	 * print out matrix
	 * @param matrix
	 */
	public void printProb(double[][] matrix){
		DecimalFormat f = new DecimalFormat("0.000");
		
		try{
			int rows = matrix.length;
			int columns = matrix[0].length;
			String str ="|\t";
			
			
			for(int i=0; i< rows; i++){
				for(int j=0; j< columns; j++){
					
					str = str + f.format(matrix[i][j])+"\t";
					
				}
				System.out.println(str+"|");
				str = "|\t";
			}
			
		}catch(Exception e){System.out.println("No Matrix found. ");}
		
		
	}
	
	
	/**
	 * print out matrix
	 * @param matrix
	 */
	public void printRoot(String [][] matrix){
		try{
			int rows = matrix.length;
			int columns = matrix[0].length;
			String str ="|\t";
			
			
			for(int i=0; i< rows; i++){
				for(int j=0; j< columns; j++){
					
					str = str + matrix[i][j]+"\t";
					
				}
				System.out.println(str+"|");
				str = "|\t";
			}
			
		}catch(Exception e){System.out.println("No Matrix found. ");}
		
		
	}

	
    public void printTree(Node node){
    	if(node == null) {
    		return;
    	}
    	//left,node itself,right
    	
    	System.out.println("Node key: " + node.key);
    	System.out.println("Node value: " + node.value);
    	System.out.println("Node Probability: " + node.probability);
    	if(node.parent!=null){
    		System.out.println("Node Parent: " + node.parent.value);
    	}else{
    		System.out.println("Parent: null" );
    	}
    	if(node.left != null){
    		System.out.println("Left Child: " + node.left.value);
    	}else{
    		System.out.println("Left Child: null" );
    	}
    	if(node.right !=null){
    		System.out.println("Right Child: " + node.right.value);
    	}
    	else{
    		System.out.println("Right Child: null" );
    	}
    	
    	System.out.println();
    	printTree(node.left);
    	printTree(node.right);
    }
	
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		ReadOptimalBST test = new ReadOptimalBST();
		List<Map.Entry <String,Double>> file = test.readFile("test_case_021.input.txt");
//		System.out.println(file.keySet());
		
		OptimalBST optimal= new OptimalBST();
		
		
		String value = optimal.probMatrix(file);
		double [][] opt= optimal.optimal;
		String [][] R=optimal.roots;
		Node node =optimal.OptimalBST(value, file);
		optimal.printTree(node);
		
		System.out.println("Probability Matrix:");
		optimal.printProb(opt);
		System.out.println();
		System.out.println("Root Matrix:");
		optimal.printRoot(R);
		
	
	}

}
